package org.leetcode.middle.leetcode647;

public class Solution {


    public int countSubstrings2(String s){

        int n  = s.length();

        boolean [][] dp = new boolean[n][n];

        int count = 1;

        dp[0][0]=true;

        for (int right = 1; right < n; right++) {
            for (int left = 0; left <= right; left++) {
                if (s.charAt(left)==s.charAt(right)){
                    if (right-left<=2 || dp[right-1][left+1]){
                        dp[right][left]=true;
                        count++;
                    }
                }
            }
        }

        return count;
    }


    public static void main(String[] args) {
        Solution test= new Solution() ;
        int abc = test.countSubstrings2("abc");
        System.out.println(abc);
    }




    //回溯失败，错误未知
    int count = 0;

    public int countSubstrings(String s) {
        backtracking(s, 0);
        return count;
    }

    private void backtracking(String s, int index) {
        if (index >= s.length()) {
            return;
        }

        for (int i = index; i < s.length(); i++) {
            if (isValid(s, index, i)) {
                count++;
                backtracking(s, i + 1);
            }
        }
    }

    private boolean isValid(String s, int start, int end) {

        if (start == end) {
            return true;
        }

        while (start <= end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }

        return true;
    }

}
